{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Insufficient Nodes in Root to Leaf Paths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sufficientSubset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #根到叶路径上的不足节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你二叉树的根节点 <code>root</code> 和一个整数 <code>limit</code> ，请你同时删除树中所有 <strong>不足节点 </strong>，并返回最终二叉树的根节点。</p>\n",
    "\n",
    "<p>假如通过节点 <code>node</code> 的每种可能的 “根-叶” 路径上值的总和全都小于给定的 <code>limit</code>，则该节点被称之为<strong> 不足节点 </strong>，需要被删除。</p>\n",
    "\n",
    "<p><strong>叶子节点</strong>，就是没有子节点的节点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/06/05/insufficient-11.png\" style=\"width: 500px; height: 207px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14], limit = 1\n",
    "<strong>输出：</strong>[1,2,3,4,null,null,7,8,9,null,14]\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/06/05/insufficient-3.png\" style=\"width: 400px; height: 274px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [5,4,8,11,null,17,4,7,1,null,null,5,3], limit = 22\n",
    "<strong>输出：</strong>[5,4,8,11,null,17,4,7,null,null,null,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/06/11/screen-shot-2019-06-11-at-83301-pm.png\" style=\"width: 250px; height: 199px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,-3,-5,null,4,null], limit = -1\n",
    "<strong>输出：</strong>[1,null,-3,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目在范围 <code>[1, 5000]</code> 内</li>\n",
    "\t<li><code>-10<sup>5</sup> &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= limit &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [insufficient-nodes-in-root-to-leaf-paths](https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [insufficient-nodes-in-root-to-leaf-paths](https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14]\\n1', '[5,4,8,11,null,17,4,7,1,null,null,5,3]\\n22', '[1,2,-3,-5,null,4,null]\\n-1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "        if root.left is root.right:\n",
    "            return None if limit>0 else root\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left,limit)\n",
    "        if root.right :\n",
    "            root.right = self.sufficientSubset(root.right,limit)\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:\n",
    "        # 计算当前节点为根节点的子节点中根节点到叶节点的最小权重之和\n",
    "        @cache\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return float('-inf')\n",
    "            if root.left is None and root.right is None:\n",
    "                return root.val \n",
    "            return max(dfs(root.left),dfs(root.right))+root.val\n",
    "\n",
    "        def fun(root,pre=0):\n",
    "            if root is None:\n",
    "                return None\n",
    "            # pre += root.val\n",
    "            if dfs(root)+pre < limit:\n",
    "                return None\n",
    "            pre += root.val\n",
    "            root.left = fun(root.left,pre)\n",
    "            root.right = fun(root.right,pre)\n",
    "            return root\n",
    "      \n",
    "        return fun(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "        if root.left is root.right:\n",
    "            return None if limit > 0 else root\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left, limit)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right, limit)\n",
    "        \n",
    "        return root if root.left or root.right else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(node,s):\n",
    "            if node is None:\n",
    "                return False\n",
    "            s += node.val\n",
    "            if node.left is None and node.right is None:\n",
    "                if s >= limit:\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            l = dfs(node.left,s)\n",
    "            r = dfs(node.right,s)\n",
    "            if not l:\n",
    "                node.left = None\n",
    "            if not r:\n",
    "                node.right = None\n",
    "            return l or r\n",
    "        ans = dfs(root,0)\n",
    "        if not ans:\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def checkSufficientLeaf(node, sum, limit):\n",
    "            if node == None:\n",
    "                return False\n",
    "            if node.left == None and node.right == None:\n",
    "                return node.val + sum >= limit\n",
    "            haveSufficientLeft = checkSufficientLeaf(node.left, sum + node.val, limit)\n",
    "            haveSufficientRight = checkSufficientLeaf(node.right, sum + node.val, limit)\n",
    "            if not haveSufficientLeft:\n",
    "                node.left = None\n",
    "            if not haveSufficientRight:\n",
    "                node.right = None\n",
    "            return haveSufficientLeft or haveSufficientRight\n",
    "        haveSufficient = checkSufficientLeaf(root, 0, limit)\n",
    "        return  root if haveSufficient else None\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "        if root.left is root.right:\n",
    "            return None if limit > 0 else root\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left, limit)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right, limit)\n",
    "        return root if root.left or root.right else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "        if root.left is root.right:  # root 是叶子\n",
    "            # 如果 limit > 0 说明从根到叶子的路径和小于 limit，删除叶子，否则不删除\n",
    "            return None if limit > 0 else root\n",
    "        if root.left: root.left = self.sufficientSubset(root.left, limit)\n",
    "        if root.right: root.right = self.sufficientSubset(root.right, limit)\n",
    "        # 如果有儿子没被删除，就不删 root，否则删 root\n",
    "        return root if root.left or root.right else None\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/insufficient-nodes-in-root-to-leaf-paths/solutions/2278769/jian-ji-xie-fa-diao-yong-zi-shen-pythonj-64lf/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(node, s):\n",
    "            s += node.val\n",
    "            if node.left is None and node.right is None:\n",
    "                return s >= limit\n",
    "            flag = 0\n",
    "            if node.left is not None:\n",
    "                v = dfs(node.left, s)\n",
    "                if not v:\n",
    "                    node.left = None\n",
    "                else:\n",
    "                    flag += 1\n",
    "            if node.right is not None:\n",
    "                v = dfs(node.right, s)\n",
    "                if not v:\n",
    "                    node.right = None\n",
    "                else:\n",
    "                    flag += 1\n",
    "            return flag != 0\n",
    "\n",
    "        if not dfs(root, 0):\n",
    "            root = None\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "        if root.left is None and root.right is None:\n",
    "            return None if limit > 0 else root\n",
    "        if root.left is not None:\n",
    "            root.left = self.sufficientSubset(root.left, limit)\n",
    "        if root.right is not None:\n",
    "            root.right = self.sufficientSubset(root.right, limit)\n",
    "        return root if root.left is not None or root.right is not None else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(node,s):\n",
    "            # 边界条件是空节点，或者是叶子节点时进行返回\n",
    "            if node is None:  \n",
    "                return False\n",
    "            s += node.val\n",
    "            if node.left is None and node.right is None:\n",
    "                if s < limit:\n",
    "                    return False\n",
    "                else:\n",
    "                    return True\n",
    "            l = dfs(node.left,s)\n",
    "            if not l:\n",
    "                node.left = None\n",
    "            r = dfs(node.right,s)\n",
    "            if not r:\n",
    "                node.right = None\n",
    "            return l or r\n",
    "        ans = dfs(root,0)\n",
    "        if ans == False:\n",
    "            return None      \n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        if not root.left and not root.right:\n",
    "            return None if root.val < limit else root\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left,limit-root.val)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right,limit-root.val)\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        # 一直向下遍历，计算两边的和即可\n",
    "        def dfs(node: Optional[TreeNode], sum: int, limit: int):\n",
    "            if node is None:\n",
    "                return False\n",
    "\n",
    "            if node.left is None and node.right is None:\n",
    "                return node.val + sum >= limit\n",
    "\n",
    "            left = dfs(node.left, sum + node.val, limit)\n",
    "            right = dfs(node.right, sum + node.val, limit)\n",
    "\n",
    "            if not left:\n",
    "                node.left = None\n",
    "\n",
    "            if not right:\n",
    "                node.right = None\n",
    "\n",
    "            return left or right\n",
    "\n",
    "        res = dfs(root, 0, limit)\n",
    "        return root if res else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "        if root.left is root.right:\n",
    "            return None if limit > 0 else root\n",
    "        if root.left: root.left = self.sufficientSubset(root.left, limit)\n",
    "        if root.right: root.right = self.sufficientSubset(root.right, limit)\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(tree, temp_sum):\n",
    "            if tree == None:\n",
    "                return False\n",
    "            if tree.left == None and tree.right == None:\n",
    "                return temp_sum + tree.val >= limit\n",
    "\n",
    "            left = dfs(tree.left, temp_sum + tree.val)\n",
    "            right = dfs(tree.right, temp_sum + tree.val)\n",
    "            \n",
    "            if tree.left and not left:\n",
    "                tree.left = None\n",
    "            if tree.right and not right:\n",
    "                tree.right = None\n",
    "            return left or right\n",
    "\n",
    "\n",
    "        flag = dfs(root, 0)\n",
    "\n",
    "        return root if flag else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "        if root.left is root.right:\n",
    "            return None if limit > 0 else root\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left,limit)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right,limit)\n",
    "        return root if root.left or root.right else None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit-=root.val\n",
    "        if root.left is None and root.right is None:\n",
    "            return None if limit>0 else root\n",
    "        if root.left:\n",
    "            root.left=self.sufficientSubset(root.left,limit)\n",
    "        if root.right:\n",
    "            root.right=self.sufficientSubset(root.right,limit)\n",
    "        return root if root.left or root.right else None            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "\n",
    "        if(root.left == root.right):\n",
    "            return None if limit > 0 else root\n",
    "        \n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left, limit)\n",
    "        \n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right, limit)\n",
    "        \n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(root, s):\n",
    "            if root.left is root.right:\n",
    "                return None if s + root.val < limit else root\n",
    "            if root.left:\n",
    "                root.left = dfs(root.left, s + root.val)\n",
    "            if root.right:\n",
    "                root.right = dfs(root.right, s + root.val)\n",
    "            return root if root.left or root.right else None\n",
    "        return dfs(root, 0)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        if (not root.left) and (not root.right): return root if limit - root.val <= 0 else None\n",
    "        if root.left: root.left = self.sufficientSubset(root.left, limit - root.val)\n",
    "        if root.right: root.right = self.sufficientSubset(root.right, limit - root.val)\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        #递归，然后就是考虑清楚这样一个问题，叶子结点是很好删除的，非叶节点删除就是要考虑只有在其子节点都删完了再删这个节点,保存和，我们可以直接让limit去－就好了，看最后叶子结点结果\n",
    "        #这个函数是得到删除后的根节点\n",
    "        if root is None:\n",
    "            return\n",
    "        limit-=root.val\n",
    "        if root.left is None and root.right is None:\n",
    "            if limit>0:\n",
    "                return None #把None传给调用的dfs函数\n",
    "            else:\n",
    "                return root\n",
    "        root.left=self.sufficientSubset(root.left,limit)\n",
    "        root.right=self.sufficientSubset(root.right,limit)\n",
    "        #对于最开始的root来说，如果子节点都被删了就返回None\n",
    "        return None if root.left is None and root.right is None else root\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "        if root.left is root.right:\n",
    "            return None if limit > 0 else root\n",
    "        if root.left: root.left = self.sufficientSubset(root.left, limit)\n",
    "        if root.right: root.right = self.sufficientSubset(root.right, limit)\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val \n",
    "        if root.left is root.right:\n",
    "            return None if limit > 0 else root \n",
    "\n",
    "        if root.left: root.left = self.sufficientSubset(root.left, limit)\n",
    "        if root.right: root.right = self.sufficientSubset(root.right, limit)\n",
    "\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        #如果节点没有任何可能使得根到叶子大于等于limit，那么就要删除它及其子树\n",
    "        limit -= root.val\n",
    "        if not root.left and not root.right:\n",
    "            return None if limit > 0 else root\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left,limit)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right, limit)\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            if root.val < limit:\n",
    "                return None\n",
    "            return root\n",
    "\n",
    "        left = self.sufficientSubset(root.left, limit - root.val)\n",
    "        right = self.sufficientSubset(root.right, limit - root.val)\n",
    "\n",
    "        if left is None and right is None:\n",
    "            return None\n",
    "\n",
    "        root.left = left\n",
    "        root.right = right\n",
    "\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        #后序遍历\n",
    "        if root.left == None and root.right == None:\n",
    "            return root if root.val >= limit else None\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left, limit - root.val)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right, limit - root.val)\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(root, limit):\n",
    "            if not root:\n",
    "                return None\n",
    "            limit -= root.val \n",
    "            if not root.left and not root.right :\n",
    "                return None if limit> 0 else root\n",
    "            root.left = dfs(root.left, limit )\n",
    "            root.right = dfs(root.right, limit)\n",
    "            \n",
    "            return None if root.left is None and root.right is None else root \n",
    "\n",
    "        return dfs(root,limit)\n",
    "       \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        if not root.left and not root.right:\n",
    "            return None if root.val < limit else root\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left,limit-root.val)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right,limit-root.val)\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "        if root.left is root.right:# 叶子\n",
    "            return None if limit > 0 else root\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left,limit)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right,limit)\n",
    "        return root if root.left or root.right else None\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def helper(node,limit,cnt):\n",
    "            if node is None:\n",
    "                return None\n",
    "            cnt = node.val+cnt\n",
    "            if node.left is None and node.right is None:\n",
    "                if cnt<limit:\n",
    "                    return None\n",
    "                else:\n",
    "                    return node\n",
    "            left = helper(node.left,limit,cnt)\n",
    "            right = helper(node.right,limit,cnt)\n",
    "            if left is None:\n",
    "                node.left = None\n",
    "            else:\n",
    "                node.left = left\n",
    "            if right is None:\n",
    "                node.right = None\n",
    "            else:\n",
    "                node.right = right\n",
    "            if node.left is None and node.right is None:\n",
    "                return None\n",
    "            else:\n",
    "                return node\n",
    "        return helper(root,limit,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        # 删除树中所有不足节点，并返回最终二叉树的根节点\n",
    "        limit -= root.val\n",
    "        # 叶子节点\n",
    "        if root.left is root.right:\n",
    "            return None if limit > 0 else root\n",
    "        if root.left:root.left = self.sufficientSubset(root.left,limit)\n",
    "        if root.right:root.right = self.sufficientSubset(root.right,limit)\n",
    "        return root if root.left or root.right else None "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(node, mx):\n",
    "            if not node:\n",
    "                return None\n",
    "            \n",
    "            mx = mx + node.val\n",
    "            left = dfs(node.left, mx)\n",
    "            if left is not None and left < limit - mx:\n",
    "                node.left = None\n",
    "            right = dfs(node.right, mx)\n",
    "            if right is not None and  right < limit - mx:\n",
    "                node.right = None\n",
    "            \n",
    "            # print(left,right)\n",
    "            res = node.val\n",
    "            if left is not None and right is not None:\n",
    "                res += max(left, right)\n",
    "            elif left is not None:\n",
    "                res += left\n",
    "            elif right is not None:\n",
    "                res += right\n",
    "\n",
    "            return res\n",
    "        \n",
    "        r = dfs(root, 0)\n",
    "        if r < limit:\n",
    "            return None\n",
    "        return root\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def f(p, c):\n",
    "            if not p:\n",
    "                return 1\n",
    "            if not p.left and not p.right:\n",
    "                if c + p.val < limit:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            l = f(p.left, c + p.val)\n",
    "            r = f(p.right, c + p.val)\n",
    "            if l:\n",
    "                p.left = None\n",
    "            if r:\n",
    "                p.right = None\n",
    "            return l & r\n",
    "        \n",
    "        if f(root, 0):\n",
    "            return None\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        \n",
    "        if not root.left and not root.right:\n",
    "            return None if limit-root.val > 0 else root\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left,limit-root.val)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right, limit-root.val)\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit -= root.val\n",
    "        if root.left is root.right:\n",
    "            if limit > 0:\n",
    "                return None\n",
    "            else:\n",
    "                return root\n",
    "        \n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left, limit)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right, limit)\n",
    "\n",
    "        if root.left or root.right:\n",
    "            return root\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(root, s):\n",
    "            if not root:\n",
    "                return None\n",
    "            if root.left is root.right:\n",
    "                return None if s + root.val < limit else root\n",
    "            root.left = dfs(root.left, s + root.val)\n",
    "            root.right = dfs(root.right, s + root.val)\n",
    "            return root if root.left or root.right else None\n",
    "        return dfs(root, 0)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        sum = 0\n",
    "        def dfs(node, pre, isleft):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal sum\n",
    "            sum += node.val\n",
    "            if not node.left and not node.right:\n",
    "                if sum < limit:\n",
    "                    if isleft:\n",
    "                        pre.left = None\n",
    "                    else:\n",
    "                        pre.right = None\n",
    "            else:\n",
    "                dfs(node.left, node, True)\n",
    "                dfs(node.right, node, False)\n",
    "                if not node.left and not node.right:\n",
    "                    if isleft:\n",
    "                        pre.left = None\n",
    "                    else:\n",
    "                        pre.right = None\n",
    "            sum -= node.val\n",
    "        \n",
    "        head = TreeNode(left=root)\n",
    "        dfs(root, head, True)\n",
    "        return head.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def recursion(node: TreeNode, _sum: int) -> bool:\n",
    "            if not node:\n",
    "                return False\n",
    "            if not node.left and not node.right:\n",
    "                return _sum + node.val >= limit\n",
    "            l = recursion(node.left, _sum + node.val)\n",
    "            r = recursion(node.right, _sum + node.val)\n",
    "            if not l:\n",
    "                node.left = None\n",
    "            if not r:\n",
    "                node.right = None\n",
    "            return l or r\n",
    "\n",
    "        t = TreeNode(left=root, val=0)\n",
    "        recursion(t, 0)\n",
    "        return t.left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def check(node, sm):\n",
    "            nonlocal limit\n",
    "            if node == None:\n",
    "                return False\n",
    "\n",
    "            if node.left == None and node.right == None:\n",
    "                return node.val + sm >= limit\n",
    "            chleft = check(node.left, node.val + sm)\n",
    "            chright = check(node.right, node.val + sm)\n",
    "        \n",
    "            if not chleft:\n",
    "                node.left = None\n",
    "            if not chright:\n",
    "                node.right = None\n",
    "\n",
    "            return chleft or chright\n",
    "        flag = check(root, 0)\n",
    "        return root if flag else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(node, s):\n",
    "            if not node:\n",
    "                return None\n",
    "            s += node.val\n",
    "            if node.left == node.right:\n",
    "                return None if s < limit else node\n",
    "            if node.left:\n",
    "                node.left = dfs(node.left, s)\n",
    "            if node.right:\n",
    "                node.right = dfs(node.right, s)\n",
    "            return node if node.left or node.right else None\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        if not root:\n",
    "            return None\n",
    "        limit -= root.val\n",
    "        if root.left is None and root.right is None:\n",
    "            return None if limit > 0 else root\n",
    "        root.left = self.sufficientSubset(root.left, limit)\n",
    "        root.right = self.sufficientSubset(root.right, limit)\n",
    "        return None if root.left is None and root.right is None else root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        dummy = TreeNode()\n",
    "        dummy.left = root\n",
    "        if not root:\n",
    "            return\n",
    "        def dfs(pre, node, v, d):\n",
    "            if not node:\n",
    "                return 0\n",
    "            else:\n",
    "                max_v = v + node.val\n",
    "                if node.left is not None and node.right is None:\n",
    "                    max_v += dfs(node, node.left, v + node.val, 0)\n",
    "                elif node.left is  None and node.right is not None:\n",
    "                    max_v += dfs(node, node.right, v + node.val, 1)\n",
    "                elif node.left is not None and node.right is not None:\n",
    "                    max_v += max(dfs(node, node.left, v + node.val, 0), dfs(node, node.right, v + node.val, 1))\n",
    "                else:\n",
    "                    pass\n",
    "                if max_v < limit:\n",
    "                    if d == 0:\n",
    "                        pre.left = None\n",
    "                    else:\n",
    "                        pre.right = None\n",
    "                return max_v - v\n",
    "        dfs(dummy, root, 0, 0)\n",
    "        return dummy.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def sufficientSubset(self, root, limit):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type limit: int\n",
    "        :rtype: TreeNode\n",
    "        \"\"\"\n",
    "        #打印二叉树的所有path\n",
    "        res = []\n",
    "        safe = {}\n",
    "        def findPath(node, tmp):\n",
    "            if not node:\n",
    "                return\n",
    "            tmp.append(node)\n",
    "            if not node.left and not node.right:\n",
    "                s = 0\n",
    "                for item in tmp:\n",
    "                    s += item.val\n",
    "                if s >= limit:\n",
    "                    for item in tmp:\n",
    "                        safe[item] = 1\n",
    "            \n",
    "            findPath(node.left, tmp)\n",
    "            findPath(node.right, tmp)\n",
    "            tmp.pop()\n",
    "            \n",
    "        findPath(root, [])\n",
    "        \n",
    "        def dfs2(node):\n",
    "            if not node:\n",
    "                return\n",
    "            if node.left and safe.get(node.left, 0) == 0:\n",
    "                node.left = None\n",
    "            if node.right and safe.get(node.right, 0) == 0:\n",
    "                node.right = None\n",
    "            dfs2(node.left)\n",
    "            dfs2(node.right)\n",
    "        dfs2(root)\n",
    "        return root if safe.get(root, 0) == 1 else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(node,cur_sum):\n",
    "            if node is None:\n",
    "                return None\n",
    "            flag=False \n",
    "            if node.left:\n",
    "                node.left=dfs(node.left,cur_sum+node.val)\n",
    "                flag=True\n",
    "            if node.right:\n",
    "                node.right=dfs(node.right,cur_sum+node.val)\n",
    "                flag=True\n",
    "            if node.left is None and node.right is None and (cur_sum+node.val<limit or flag):\n",
    "                return None\n",
    "            return node\n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(node, limit, total):\n",
    "            if not node:\n",
    "                return False\n",
    "            if not node.left and not node.right:\n",
    "                return node.val + total >= limit\n",
    "\n",
    "            left = dfs(node.left, limit, total+node.val)\n",
    "            right = dfs(node.right, limit, total+node.val)\n",
    "\n",
    "            if not left:\n",
    "                node.left = None\n",
    "            if not right:\n",
    "                node.right = None\n",
    "\n",
    "            return left or right\n",
    "\n",
    "        return root if dfs(root, limit, 0) else None\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(node,cur_sum):\n",
    "            if node is None:\n",
    "                return None\n",
    "            flag=False \n",
    "            if node.left:\n",
    "                node.left=dfs(node.left,cur_sum+node.val)\n",
    "                flag=True\n",
    "            if node.right:\n",
    "                node.right=dfs(node.right,cur_sum+node.val)\n",
    "                flag=True\n",
    "            if node.left is None and node.right is None and (cur_sum+node.val<limit or flag):\n",
    "                return None\n",
    "            return node\n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(node, running_sum):\n",
    "            if not node:\n",
    "                return None\n",
    "\n",
    "            running_sum += node.val\n",
    "\n",
    "            # 如果是叶子节点，并且路径上的和小于 limit，则返回 None 标记删除\n",
    "            if not node.left and not node.right:\n",
    "                return None if running_sum < limit else node\n",
    "\n",
    "            # 递归处理左右子树\n",
    "            node.left = dfs(node.left, running_sum)\n",
    "            node.right = dfs(node.right, running_sum)\n",
    "\n",
    "            # 如果左右子树都被删除，则当前节点也要删除\n",
    "            if not node.left and not node.right:\n",
    "                return None\n",
    "\n",
    "            return node\n",
    "\n",
    "        return dfs(root, 0)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        \n",
    "        def dfs(node, sums):\n",
    "            if node is None:return False\n",
    "            if node.left is None and node.right is None:\n",
    "                return sums+node.val >= limit\n",
    "            \n",
    "            check_left = dfs(node.left, sums+node.val)\n",
    "            check_right = dfs(node.right, sums+node.val)\n",
    "\n",
    "            if not check_left:\n",
    "                node.left = None\n",
    "            if not check_right:\n",
    "                node.right = None\n",
    "            return check_left or check_right\n",
    "\n",
    "        roocheck = dfs(root, 0)\n",
    "        return root if roocheck else None\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(node,cur_sum):\n",
    "            if node is None:\n",
    "                return None\n",
    "            flag=False \n",
    "            if node.left:\n",
    "                node.left=dfs(node.left,cur_sum+node.val)\n",
    "                flag=True\n",
    "            if node.right:\n",
    "                node.right=dfs(node.right,cur_sum+node.val)\n",
    "                flag=True\n",
    "            if node.left is None and node.right is None and (cur_sum+node.val<limit or flag):\n",
    "                return None\n",
    "            return node\n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(node,cur_sum):\n",
    "            if node is None:\n",
    "                return None\n",
    "            flag=False \n",
    "            if node.left:\n",
    "                node.left=dfs(node.left,cur_sum+node.val)\n",
    "                flag=True\n",
    "            if node.right:\n",
    "                node.right=dfs(node.right,cur_sum+node.val)\n",
    "                flag=True\n",
    "            if node.left is None and node.right is None and (cur_sum+node.val<limit or flag):\n",
    "                return None\n",
    "            return node\n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def rm_node(root, limit):\n",
    "            if root is None:\n",
    "                return limit\n",
    "            if root.left is None and root.right is None:\n",
    "                return limit - root.val\n",
    "            min_val = 1e10\n",
    "            if root.left is not None:\n",
    "                temp = rm_node(root.left, limit - root.val)\n",
    "                if temp > 0:\n",
    "                    root.left = None\n",
    "                min_val = min(min_val, temp)\n",
    "            if root.right is not None:\n",
    "                temp = rm_node(root.right, limit - root.val)\n",
    "                if temp > 0:\n",
    "                    root.right = None\n",
    "                min_val = min(min_val, temp)\n",
    "            return min_val\n",
    "        temp = rm_node(root, limit)\n",
    "        if temp > 0:\n",
    "            return None\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def checkSufficientLeaf(node,sum,limit):\n",
    "            if  node == None:\n",
    "                return False \n",
    "            if node.left == None and node.right == None:\n",
    "                return sum + node.val >= limit\n",
    "            \n",
    "            haveSufficientLeft = checkSufficientLeaf(node.left,sum+node.val,limit)\n",
    "            haveSufficientRight = checkSufficientLeaf(node.right,sum+node.val,limit)\n",
    "\n",
    "            if not haveSufficientLeft:\n",
    "                node.left = None\n",
    "            if not haveSufficientRight:\n",
    "                node.right = None\n",
    "            \n",
    "            return haveSufficientLeft or haveSufficientRight\n",
    "        \n",
    "        haveSufficien = checkSufficientLeaf(root,0,limit)\n",
    "        return root if haveSufficien else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        if root == None:\n",
    "            return None\n",
    "        if root.left == None and root.right == None:\n",
    "            return root if root.val >= limit else None\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left, limit - root.val)\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right, limit - root.val)\n",
    "        return root if root.left or root.right else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(node, theSum):\n",
    "            theSum += node.val\n",
    "            if node.left is None and node.right is None:\n",
    "                return theSum < limit\n",
    "            left_insuff = dfs(node.left, theSum) if node.left else True\n",
    "            right_insuff = dfs(node.right, theSum) if node.right else True\n",
    "            if left_insuff:\n",
    "                node.left = None\n",
    "            if right_insuff:\n",
    "                node.right = None\n",
    "            return left_insuff and right_insuff\n",
    "\n",
    "        ret = dfs(root, 0)\n",
    "        return None if ret else root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def checkSufficientLeaf(node, sum, limit):\n",
    "            if node == None:\n",
    "                return False\n",
    "            if node.left == None and node.right == None:\n",
    "                return node.val + sum >= limit\n",
    "            haveSufficientLeft = checkSufficientLeaf(node.left, sum + node.val, limit)\n",
    "            haveSufficientRight = checkSufficientLeaf(node.right, sum + node.val, limit)\n",
    "            if not haveSufficientLeft:\n",
    "                node.left = None\n",
    "            if not haveSufficientRight:\n",
    "                node.right = None\n",
    "            return haveSufficientLeft or haveSufficientRight\n",
    "        haveSufficient = checkSufficientLeaf(root, 0, limit)\n",
    "        return  root if haveSufficient else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        pre = 0\n",
    "        def dfs(root):\n",
    "            nonlocal pre\n",
    "            if not root:\n",
    "                return False\n",
    "            if not root.left and not root.right:\n",
    "                return root.val + pre >= limit\n",
    "            \n",
    "            pre += root.val\n",
    "            flagL = dfs(root.left)\n",
    "            if not flagL:   root.left = None \n",
    "            flagR = dfs(root.right)\n",
    "            if not flagR:   root.right = None\n",
    "            pre -= root.val\n",
    "            return flagL or flagR\n",
    "        \n",
    "        head = TreeNode(0, left = root)\n",
    "        dfs(head)\n",
    "        return head.left\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(node, s):\n",
    "            if node is None:\n",
    "                return None\n",
    "            s += node.val\n",
    "            if node.left is None and node.right is None:\n",
    "                return None if s < limit else node\n",
    "            node.left = dfs(node.left, s)\n",
    "            node.right = dfs(node.right, s)\n",
    "            return node if node.left or node.right else None \n",
    "\n",
    "        return dfs(root, 0)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def checkSufficientLeaf(node, sum, limit):\n",
    "            if node == None:\n",
    "                return False\n",
    "            if node.left == None and node.right == None:\n",
    "                return node.val + sum >= limit\n",
    "            haveSufficientLeft = checkSufficientLeaf(node.left, sum + node.val, limit)\n",
    "            haveSufficientRight = checkSufficientLeaf(node.right, sum + node.val, limit)\n",
    "            if not haveSufficientLeft:\n",
    "                node.left = None\n",
    "            if not haveSufficientRight:\n",
    "                node.right = None\n",
    "            return haveSufficientLeft or haveSufficientRight\n",
    "        haveSufficient = checkSufficientLeaf(root, 0, limit)\n",
    "        return  root if haveSufficient else None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(root, curnum):\n",
    "            nonlocal limit\n",
    "            curnum += root.val\n",
    "            if not root.left and not root.right:\n",
    "                return curnum >= limit\n",
    "            boolleft, boolright = False, False\n",
    "            if root.left:\n",
    "                boolleft = dfs(root.left, curnum)\n",
    "            if root.right:\n",
    "                boolright = dfs(root.right, curnum)\n",
    "            if not (boolleft or boolright):\n",
    "                root.left = None\n",
    "                root.right = None\n",
    "                return False\n",
    "            elif not boolleft:\n",
    "                root.left = None\n",
    "                return True\n",
    "            elif not boolright:\n",
    "                root.right = None\n",
    "                return True\n",
    "            else:\n",
    "                return True\n",
    "        if dfs(root, 0):\n",
    "            return root\n",
    "        return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(root, sums):\n",
    "            if root.left is None and root.right is None:\n",
    "                return None if sums < limit else root\n",
    "            if root.left:\n",
    "                root.left = dfs(root.left, sums+root.left.val)\n",
    "            if root.right:\n",
    "                root.right = dfs(root.right, sums+root.right.val)\n",
    "            # 非叶子节点\n",
    "            return root if root.left or root.right else None\n",
    "            \n",
    "        root = dfs(root, root.val)\n",
    "        return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        self.nodes1 = {}\n",
    "        self.nodes2 = {}\n",
    "        self.dfs(root, limit, [], 0)\n",
    "\n",
    "        if self.nodes1:\n",
    "            for node in self.nodes2:\n",
    "                self.nodes1[node] = False\n",
    "        \n",
    "        return self.dfs2(root)\n",
    "\n",
    "    def dfs(self, node: TreeNode, limit: int, path: List[TreeNode], total: int):\n",
    "        if not node:\n",
    "            return\n",
    "\n",
    "        path.append(node)\n",
    "        total += node.val\n",
    "\n",
    "        self.dfs(node.left, limit, path, total)\n",
    "        self.dfs(node.right, limit, path, total)\n",
    "\n",
    "        if not node.left and not node.right:\n",
    "            if total < limit:\n",
    "                for n in path:\n",
    "                    self.nodes1[n] = True\n",
    "            else:\n",
    "                for n in path:\n",
    "                    self.nodes2[n] = n\n",
    "\n",
    "        total -= node.val\n",
    "        path.pop(len(path) - 1)\n",
    "    \n",
    "    def dfs2(self, node: TreeNode) -> TreeNode:\n",
    "        if not node:\n",
    "            return None\n",
    "        if node in self.nodes1 and self.nodes1[node]:\n",
    "            return None\n",
    "        node.left = self.dfs2(node.left)\n",
    "        node.right = self.dfs2(node.right)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        # 先打标签是否需要删除\n",
    "        # 然后再遍历删除\n",
    "        tmp = [limit]\n",
    "        def tag(root, _sum):\n",
    "            if not root:\n",
    "                return 0\n",
    "            new_sum = _sum + root.val\n",
    "            if not root.left and not root.right:\n",
    "                root.tag = int(new_sum >= tmp[0])\n",
    "                return int(new_sum >= tmp[0])\n",
    "            else:\n",
    "                root.tag = max(tag(root.left, new_sum), tag(root.right, new_sum))\n",
    "                return root.tag\n",
    "        \n",
    "        def print_tag(root):\n",
    "            if not root:\n",
    "                return\n",
    "            print(root.tag)\n",
    "            print_tag(root.left)\n",
    "            print_tag(root.right)\n",
    "\n",
    "        def _del(root):\n",
    "            if not root or root.tag == 0:\n",
    "                return None\n",
    "\n",
    "            if root.left:\n",
    "                if root.left.tag == 0:\n",
    "                    root.left = None\n",
    "                else:\n",
    "                    _del(root.left)\n",
    "            if root.right:\n",
    "                if root.right.tag == 0:\n",
    "                    root.right = None\n",
    "                else:\n",
    "                    _del(root.right)\n",
    "            \n",
    "            return root\n",
    "        \n",
    "        tag(root, 0)\n",
    "        print_tag(root)\n",
    "        root = _del(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        s = 0\n",
    "        def dfs(node, s):\n",
    "            if not node:\n",
    "                return\n",
    "            s += node.val\n",
    "            if node.left == None and node.right == None:\n",
    "                if s >= limit: \n",
    "                    return node\n",
    "                else:\n",
    "                    return None\n",
    "            node.left = dfs(node.left, s)\n",
    "            node.right = dfs(node.right, s)\n",
    "            if node.left == None and node.right == None:\n",
    "                return None\n",
    "            else:\n",
    "                return node\n",
    "        a = dfs(root, s)\n",
    "        return a \n",
    "        # if root is None:\n",
    "        #     return None\n",
    "        # limit -= root.val\n",
    "        # if root.left is None and root.right is None:\n",
    "        #     return None if limit > 0 else root\n",
    "        # root.left = self.sufficientSubset(root.left, limit)\n",
    "        # root.right = self.sufficientSubset(root.right, limit)\n",
    "        # return None if root.left is None and root.right is None else root\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\r\n",
    "        \r\n",
    "        def dfs(node, cnt):\r\n",
    "            \r\n",
    "            if node.left is None and node.right is None:\r\n",
    "                return cnt + node.val < limit\r\n",
    "            \r\n",
    "            left_del = True\r\n",
    "            right_del = True\r\n",
    "            \r\n",
    "            if node.left:\r\n",
    "                left_del = dfs(node.left,cnt + node.val)\r\n",
    "            \r\n",
    "            if node.right:\r\n",
    "                right_del = dfs(node.right,cnt + node.val)\r\n",
    "            \r\n",
    "            \r\n",
    "            if left_del:\r\n",
    "                node.left = None\r\n",
    "            \r\n",
    "            if right_del:\r\n",
    "                node.right = None\r\n",
    "            \r\n",
    "            \r\n",
    "            return left_del and right_del\r\n",
    "        \r\n",
    "        root_del = dfs(root, 0)\r\n",
    "        if root_del:\r\n",
    "           return None \r\n",
    "        \r\n",
    "        return root\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def f(node: Optional[TreeNode], true_limit: int):\n",
    "            if node.left is None and node.right is None:\n",
    "                if node.val < true_limit:\n",
    "                    return -inf\n",
    "                return node.val\n",
    "            left_sum = right_sum = -inf\n",
    "            if node.left: \n",
    "                left_sum = f(node.left, true_limit-node.val)\n",
    "                if left_sum == -inf:\n",
    "                    node.left = None\n",
    "            if node.right: \n",
    "                right_sum = f(node.right, true_limit-node.val)\n",
    "                if right_sum == -inf:\n",
    "                    node.right = None\n",
    "            # if max(left_sum, right_sum) + node.val < true_limit:\n",
    "            #     return -inf\n",
    "            return max(left_sum, right_sum) + node.val\n",
    "        \n",
    "        if f(root, limit) == -inf:\n",
    "            return None\n",
    "        else: return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # def __init__(self):\n",
    "    #     self.pathSum = 0\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def helper(root, currSum, limit): \n",
    "            if not root:\n",
    "                return None, currSum\n",
    "            currSum += root.val  \n",
    "         \n",
    "            if not root.left and not root.right:\n",
    "                if currSum < limit:\n",
    "                    return None, currSum\n",
    "                else:\n",
    "                    return root, currSum\n",
    "\n",
    "            leftSum = -math.inf \n",
    "            rightSum = -math.inf \n",
    "            if root.left:\n",
    "                root.left, leftSum = helper(root.left, currSum, limit)\n",
    "            if root.right:\n",
    "                root.right, rightSum = helper(root.right, currSum, limit)\n",
    "\n",
    "            if leftSum < limit and rightSum < limit:\n",
    "                return None, -math.inf\n",
    "\n",
    "            return root, max(leftSum, rightSum)\n",
    "\n",
    "            \n",
    "        # print(helper(root, 0, limit))\n",
    "        return helper(root, 0, limit)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def dfs(node, v):\n",
    "            \n",
    "            if not node:\n",
    "                return \n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                return node if v+node.val >= limit else None\n",
    "\n",
    "            node.left = dfs(node.left, v+node.val)\n",
    "            node.right = dfs(node.right, v+node.val)\n",
    "            \n",
    "            return node if node.left or node.right else None\n",
    "            \n",
    "        return dfs(root, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        #判定方法：到此节点的前缀和+max(子节点后缀和)<阈值\n",
    "        QianZhuiHe={None:0}\n",
    "        HouZhuiHeMAX={None:0}\n",
    "        def QianZhuiHe_DFS(root,Dict):\n",
    "            Stack=[[root,0]]\n",
    "            while len(Stack):\n",
    "                Current=Stack.pop(-1)\n",
    "                LuJingHe=Current[1]+Current[0].val\n",
    "                Dict[Current[0]]=LuJingHe\n",
    "                if Current[0].left:\n",
    "                    Stack.append([Current[0].left,LuJingHe])\n",
    "                if Current[0].right:\n",
    "                    Stack.append([Current[0].right,LuJingHe])\n",
    "        def HouZhuiHeMAX_DiGui(root,Dict):\n",
    "            if root==None:\n",
    "                return 0\n",
    "            else:\n",
    "                LSUM=HouZhuiHeMAX_DiGui(root.left,Dict)\n",
    "                RSUM=HouZhuiHeMAX_DiGui(root.right,Dict)\n",
    "                if root.left and root.right==None:\n",
    "                    RSUM=-10000000000\n",
    "                if root.right and root.left==None:\n",
    "                    LSUM=-10000000000\n",
    "                HouZhuiHe=root.val+max(LSUM,RSUM)\n",
    "                Dict[root]=HouZhuiHe\n",
    "                return HouZhuiHe\n",
    "        QianZhuiHe_DFS(root,QianZhuiHe)\n",
    "        HouZhuiHeMAX_DiGui(root,HouZhuiHeMAX)\n",
    "        #print(HouZhuiHeMAX)\n",
    "        #再DFS\n",
    "        if QianZhuiHe[root]+max(HouZhuiHeMAX[root.left],HouZhuiHeMAX[root.right])<limit:\n",
    "            return None\n",
    "        else:\n",
    "            Stack=[root]\n",
    "            while len(Stack):\n",
    "                Current=Stack.pop(-1)\n",
    "                if QianZhuiHe[Current]+HouZhuiHeMAX[Current.left]>=limit and Current.left:\n",
    "                    Stack.append(Current.left)\n",
    "                else:\n",
    "                    Current.left=None\n",
    "                if QianZhuiHe[Current]+HouZhuiHeMAX[Current.right]>=limit and Current.right:\n",
    "                    Stack.append(Current.right)\n",
    "                else:\n",
    "                    Current.right=None\n",
    "            return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        self.limit = limit\n",
    "        ret = self.backtracking(root, root.val)\n",
    "        if ret:\n",
    "            return root\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "    def backtracking(self, root, above):\n",
    "        # print(above)\n",
    "        if not root.left and not root.right:\n",
    "            if above >= self.limit:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        retl=None\n",
    "        retr=None\n",
    "        if root.left:\n",
    "            retl = self.backtracking(root.left, above+root.left.val)\n",
    "            if not retl:\n",
    "                root.left = None\n",
    "        if root.right:\n",
    "            retr = self.backtracking(root.right, above+root.right.val)\n",
    "            if not retr:\n",
    "                root.right = None\n",
    "        # print(root.val, retl, retr)\n",
    "        if (retl == True) or (retr == True):\n",
    "            return True\n",
    "        return False\n",
    "        \n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]: \n",
    "        limit -= root.val\n",
    "        if not root.left and not root.right:\n",
    "            return None if limit > 0 else root\n",
    "\n",
    "        if root.left:\n",
    "            root.left = self.sufficientSubset(root.left, limit)\n",
    "\n",
    "        if root.right:\n",
    "            root.right = self.sufficientSubset(root.right, limit)\n",
    "\n",
    "        if not root.left and not root.right:\n",
    "            return None\n",
    "        \n",
    "        return root\n",
    "     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class TreeNode2:\n",
    "    def __init__(self, x, s):\n",
    "        self.val=x\n",
    "        self.sum=s\n",
    "        self.left=None\n",
    "        self.right=None\n",
    "\n",
    "class Solution:\n",
    "    root2=None\n",
    "    def dfs(self, newroot:Optional[TreeNode2], root:Optional[TreeNode]):\n",
    "        if not root or not newroot:\n",
    "            return 0\n",
    "        newroot.sum=root.val+max(self.dfs(newroot.left, root.left), self.dfs(newroot.right, root.right))\n",
    "        return newroot.sum\n",
    "\n",
    "    def buildTree(self, root:Optional[TreeNode]):\n",
    "        if not root:\n",
    "            return None,0\n",
    "        newroot=TreeNode2(-1,-1)\n",
    "        newroot.left,vl=self.buildTree(root.left)\n",
    "        newroot.right,vr=self.buildTree(root.right)\n",
    "        newroot.val=root.val\n",
    "        newroot.sum=root.val+max(vl, vr)\n",
    "        return newroot, newroot.sum\n",
    "\n",
    "    def func(self,newroot:Optional[TreeNode2], root:Optional[TreeNode], limit:int):\n",
    "        if not newroot or not root:\n",
    "            return None\n",
    "        if newroot.sum<limit:\n",
    "            return None\n",
    "        root.left=self.func(newroot.left, root.left, limit)\n",
    "        root.right=self.func(newroot.right, root.right, limit)\n",
    "        return root\n",
    "\n",
    "    def preorder(self, newroot:Optional[TreeNode2]):\n",
    "        if not newroot:\n",
    "            return None\n",
    "        print(newroot.sum)\n",
    "        self.preorder(newroot.left)\n",
    "        self.preorder(newroot.right)\n",
    "\n",
    "    def sufficientSubset1(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        self.root2=self.buildTree(root)\n",
    "        # self.preorder(self.root2)\n",
    "        # self.dfs(self.root2, root)\n",
    "        # self.preorder(self.root2)\n",
    "        return self.func(self.root2, root, limit)\n",
    "\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit-=root.val\n",
    "        if root.left is root.right:\n",
    "            return None if limit>0 else root\n",
    "        if root.left:\n",
    "            root.left=self.sufficientSubset(root.left,limit)\n",
    "        if root.right:\n",
    "            root.right=self.sufficientSubset(root.right,limit)\n",
    "        return root if root.left or root.right else None\n",
    "\n",
    "class Solution1080:\n",
    "    root2=None\n",
    "    def dfs(self, newroot:Optional[TreeNode2], root:Optional[TreeNode]):\n",
    "        if not root or not newroot:\n",
    "            return 0\n",
    "        newroot.sum=root.val+max(self.dfs(newroot.left, root.left), self.dfs(newroot.right, root.right))\n",
    "        return newroot.sum\n",
    "\n",
    "    def buildTree(self, root:Optional[TreeNode]):\n",
    "        if not root:\n",
    "            return None,0\n",
    "        newroot=TreeNode2(-1,-1)\n",
    "        newroot.left,vl=self.buildTree(root.left)\n",
    "        newroot.right,vr=self.buildTree(root.right)\n",
    "        newroot.val=root.val\n",
    "        newroot.sum=root.val+max(vl, vr)\n",
    "        return newroot, newroot.sum\n",
    "\n",
    "    def func(self,newroot:Optional[TreeNode2], root:Optional[TreeNode], limit:int):\n",
    "        if not newroot or not root:\n",
    "            return None\n",
    "        if newroot.sum<limit:\n",
    "            return None\n",
    "        root.left=self.func(newroot.left, root.left, limit)\n",
    "        root.right=self.func(newroot.right, root.right, limit)\n",
    "        return root\n",
    "\n",
    "    def preorder(self, newroot:Optional[TreeNode2]):\n",
    "        if not newroot:\n",
    "            return None\n",
    "        print(newroot.sum)\n",
    "        self.preorder(newroot.left)\n",
    "        self.preorder(newroot.right)\n",
    "\n",
    "    def sufficientSubset1(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        self.root2=self.buildTree(root)\n",
    "        # self.preorder(self.root2)\n",
    "        # self.dfs(self.root2, root)\n",
    "        # self.preorder(self.root2)\n",
    "        return self.func(self.root2, root, limit)\n",
    "\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        limit-=root.val\n",
    "        if root.left is root.right:\n",
    "            return None if limit>0 else root\n",
    "        if root.left:\n",
    "            root.left=self.sufficientSubset(root.left,limit)\n",
    "        if root.right:\n",
    "            root.right=self.sufficientSubset(root.right,limit)\n",
    "        return root if root.left or root.right else None\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "\n",
    "        def OnSideMax(root,upsum):\n",
    "            # if not root:\n",
    "                # return 0\n",
    "            m=-float('inf')\n",
    "            if not root.left and not root.right:\n",
    "                return root.val\n",
    "            if root.left:\n",
    "                left = OnSideMax(root.left, upsum+root.val)\n",
    "                l_sum = left + root.val + upsum\n",
    "                if l_sum < limit:\n",
    "                    root.left = None\n",
    "                m=max(m,left)\n",
    "            if root.right:\n",
    "                right = OnSideMax(root.right, upsum+root.val)\n",
    "                r_sum = right + root.val + upsum\n",
    "                if r_sum < limit:\n",
    "                    root.right = None\n",
    "                m=max(m,right)\n",
    "            s=root.val\n",
    "            print('node',root.val,m)\n",
    "            if m+root.val<limit:\n",
    "                print('et')\n",
    "                root=None\n",
    "            return m + s\n",
    "        if(OnSideMax(root, 0)<limit):\n",
    "            return None\n",
    "        print(root)\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        valDict = collections.defaultdict(int)\n",
    "        pre = 0\n",
    "        def dfs(root):\n",
    "            nonlocal pre\n",
    "            if not root:\n",
    "                return\n",
    "            \n",
    "            pre += root.val\n",
    "            valDict[root] = pre\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            pre -= root.val\n",
    "        \n",
    "        def reverseDfs(root, parent):\n",
    "            if not root:\n",
    "                return -10**9\n",
    "            \n",
    "            child = max(reverseDfs(root.left, root), reverseDfs(root.right, root))\n",
    "            if child == -10**9: child = 0\n",
    "\n",
    "            if valDict[root] + child < limit:\n",
    "                if parent.left == root: parent.left = None\n",
    "                else:   parent.right = None\n",
    "            \n",
    "            return child + root.val\n",
    "        dfs(root)\n",
    "        head = TreeNode(0, left=root)\n",
    "        reverseDfs(root, head)\n",
    "        return head.left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        self.nodes1 = {}\n",
    "        self.nodes2 = {}\n",
    "        self.dfs(root, limit, [], 0)\n",
    "\n",
    "        for node in self.nodes2:\n",
    "            if node in self.nodes1:\n",
    "                del self.nodes1[node]\n",
    "        \n",
    "        return self.dfs2(root)\n",
    "\n",
    "    def dfs(self, node: TreeNode, limit: int, path: List[TreeNode], total: int):\n",
    "        if not node:\n",
    "            return\n",
    "\n",
    "        path.append(node)\n",
    "        total += node.val\n",
    "\n",
    "        self.dfs(node.left, limit, path, total)\n",
    "        self.dfs(node.right, limit, path, total)\n",
    "\n",
    "        if not node.left and not node.right:\n",
    "            if total < limit:\n",
    "                for n in path:\n",
    "                    self.nodes1[n] = n\n",
    "            else:\n",
    "                for n in path:\n",
    "                    self.nodes2[n] = n\n",
    "\n",
    "        total -= node.val\n",
    "        path.pop(len(path) - 1)\n",
    "    \n",
    "    def dfs2(self, node: TreeNode) -> TreeNode:\n",
    "        if not node:\n",
    "            return None\n",
    "        if node in self.nodes1:\n",
    "            return None\n",
    "        node.left = self.dfs2(node.left)\n",
    "        node.right = self.dfs2(node.right)\n",
    "        return node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sufficientSubset(self, root: Optional[TreeNode], limit: int) -> Optional[TreeNode]:\n",
    "        def dfs(node, now_sum):\n",
    "            if node.left == None and node.right == None:\n",
    "                return now_sum + node.val\n",
    "            \n",
    "            left_dfs,right_dfs = -float(\"inf\"), -float(\"inf\")\n",
    "            if node.left != None:\n",
    "                left_dfs = dfs(node.left, now_sum + node.val)\n",
    "                if left_dfs < limit:\n",
    "                    node.left = None\n",
    "\n",
    "            if node.right != None:\n",
    "                right_dfs = dfs(node.right, now_sum + node.val)\n",
    "                if right_dfs < limit:\n",
    "                    node.right = None\n",
    "\n",
    "            \n",
    "            print(node.val,max(left_dfs,right_dfs),left_dfs,right_dfs)\n",
    "\n",
    "\n",
    "\n",
    "            return max(left_dfs,right_dfs)\n",
    "            \n",
    "\n",
    "        if dfs(root, 0) <limit:\n",
    "            return None\n",
    "        return root\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
